#include <list>
#include <sstream>

#include "../tools/pce/PCE.h"

using ::std::list;

template< class T >
class Graph
{
public:
    virtual void insert_edge( int v1, int v2, T w = 1 ) = 0;
    virtual void remove_edge( int v1, int v2 ) = 0;
    virtual T get_edge( int v1, int v2 ) = 0;
    virtual int get_edge_num() = 0;
    virtual int get_vertex_num() = 0;
    virtual ::std::string to_string() = 0;
};

template< class T >
class GraphMatrix : public Graph< T >
{
public:
    GraphMatrix( int vnum )
    {
        vertex_num = vnum;
        edge_matrix = new T*[vnum];
        edge_matrix[0] = new T[vnum*vnum];
        for (int i = 1; i < vnum; ++i)
        {
            edge_matrix[i] = edge_matrix[i-1] + vnum;
        }
        memset(edge_matrix[0], 0, vertex_num*vertex_num*sizeof(T));
    }

    ~GraphMatrix()
    {
        delete[] edge_matrix[0];
        delete[] edge_matrix;
    }

    void insert_edge( int v1, int v2, T w = 1 )
    {
        edge_matrix[v1][v2] = w;
        edge_num++;
    }

    void remove_edge( int v1, int v2 )
    {
        edge_matrix[v1][v2] = 0;
        edge_num--;
    }

    T get_edge( int v1, int v2 )
    {
        return edge_matrix[v1][v2];
    }

    int get_edge_num()
    {
        return edge_num;
    }

    int get_vertex_num()
    {
        return vertex_num;
    }

    ::std::string to_string()
    {
        ::std::ostringstream out_str;
        for (int i = 0; i < vertex_num; ++i)
        {
            out_str << '\t' << i;
        }
        out_str << '\n';
        for (int i = 0; i < vertex_num; ++i)
        {
            out_str << i;
            for (int j = 0; j < vertex_num; ++j)
            {
                out_str << '\t' << edge_matrix[i][j];
            }
            out_str << '\n';
        }
        return out_str.str();
    }
  
private:
    T** edge_matrix;
    int vertex_num;
    int edge_num;
};

template < class T >
class GraphList : public Graph< T >
{
public:
    class Edge
    {
    public:
        Edge( int v1, int v2, T w = 1 ):v1(v1), v2(v2), w(w){ }
        bool operator== ( const Edge& ee ) const
        {
            return v1 == ee.v1 && v2 == ee.v2;
        }

    public:
        int v1, v2;
        T w;
    };
  
public:
    GraphList( int vnum )
    {
        vertex_num = vnum;
        edge_list = new list< Edge >[vnum];
    }

    ~GraphList()
    {
        for (size_t i = 0; i < vertex_num; ++i)
        {
            edge_list[i].clear();
        }
        delete[] edge_list;
    }

    void insert_edge( int v1, int v2, T w = 1 )
    {
        assert( v1 < vertex_num && v2 < vertex_num );
        Edge e( v1, v2, w );
        edge_list[v1].push_back( e );
        edge_num++;
    }

    void remove_edge( int v1, int v2 )
    {
        assert( v1 < vertex_num && v2 < vertex_num );
        Edge e( v1, v2 );
        edge_list[v1].remove( e );
        edge_num--;
    }

    T get_edge( int v1, int v2 )
    {
        assert( v1 < vertex_num && v2 < vertex_num );
        Edge e( v1, v2 );
        list< Edge > t1 = edge_list[v1];
        typename list< Edge >::iterator cit;
        for( cit = t1.begin(); cit != t1.end(); cit++ ){
            if( *cit == e )
                return cit->w;
        }
        return (T)0;
    }

    int get_vertex_num()
    {
        return vertex_num;
    }

    int get_edge_num()
    {
        return edge_num;
    }

    ::std::string to_string()
    {
        ::std::ostringstream out_str;
        for( size_t i = 0; i < vertex_num; i++ ){
            out_str << i << '\t';
            list< Edge > t1 = edge_list[i];
            typename list< Edge >::iterator cit;
            for( cit = t1.begin(); cit != t1.end(); cit++ ){
                out_str << cit->v2 << '\t';
            }
            out_str << '\n';
        }

        return out_str.str();
    }
  
private:
    list< Edge > *edge_list;
    unsigned int vertex_num;
    unsigned int edge_num;
};

